This invention relates to data processing systems wherein the operating systems operate on the concept of virtual memory. More particularly, it relates to apparatus for managing and evaluating such memories in an operating environment.
In recent years, several types of data processing apparatus operate based upon the concept of a virtual memory, such memory employing a combination of a smaller high speed main storage, and a larger and relatively slower secondary storage. The virtual memory makes use of the secondary storage by giving it virtual addresses above the limits of the main storage. The operating system in a virtual memory machine operates as if the secondary storage is as an extension of the high speed main storage by the use of "paging." By "paging," there is meant the bringing of a page of information in secondary storage into main storage at the time that it is required.
Concomitantly with the development of virtual memories which employ a demand paging technique, there have been developed replacement algorithms which are utilized to determine which page is to be removed from main storage and placed back into secondary storage if main storage overflows. Such replacement algorithms have utilized various criteria for determining the choice of page removal, examples of such criteria being first-in first-out (FIFO), least recently used (LRU) and others. In a demand paging type of system, frequently a page which is required is not available in main storage; such unavailability being termed a "page fault."
Quite early in the development of virtual machines employing paging, and replacement algorithms for use in such virtual machines, it was recognized that given a program by its reference string and the size of the main memory, it is useful to known the minimum number of page faults necessary to run the program for evaluating memory configurations and/or algorithms. The minimum number of page faults divided by the number of faults generated by a replacement algorithm is then defined as the efficiency of this particular algorithm. Efficiencies have since been extensively measured and found to vary widely between about 0.15 and 1.0, an approximate average being about 0.4.
To determine the minimum number of page faults, there have been developed the so-called MIN algorithm and the OPT algorithm. The MIN algorithm is described in the publication of L. A. Belady, "A Study of Replacement Algorithms for Virtual Storage Computers," IBM Systems Journal, Vo. 5, No. 2, June 1966. This algorithm enables the continuous processing of the reference string and, given a fixed memory size, computes a single minimum value by constructing, with necessary and variable delay, the memory states and their transitions. The disadvantage presented by this MIN algorithm is that it works for a single memory size at a time.
To overcome this disadvantage, the OPT algorithm was developed, the latter algorithm is described in the publication of R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Systems Journal, Vol. 9, No. 2, June 1970. This OPT algorithm computes the minimum page fault count for the entire range of memory sizes substantially concurrently. The disadvantage presented in the use of the OPT algorithm is that it requires repetitious look-ahead which then has to be eliminated by a pre-processing first pass. This first pass is the construction of the LRU (least recently used) distance string, usually performed in the reverse order. The resulting sequence is subsequently processed by the OPT algorithm to compute its distance string, i.e., the sequence of minimum capacity memories.
In considering the foregoing described MIN and OPT algorithms, it has been found that both are useful in given situations. Thus, the MIN algorithm is a simple, continuous and efficient technique when only a single memory size is of interest and may be frequently employed in compilers for register allocation. Such use is described in the publication of F. R. A. Hopgood, "Compiling Techniques," MacDonald: London, 1970; pp. 96-99, and in the publication of D. Gries, "Compiler Construction for Digital Computers," John Wiley and Sons, New York 1972. The OPT algorithm, however, is more elaborate, and requires larger amounts of recorded information but it is efficaccious in that it directly provides information as to the entire space-time behavior of the program. Consequently, the OPT algorithm is extensively employed to evaluate storage hierarchy configurations.
However, neither of the MIN or OPT algorithms can be used as an on-line device in an operational environment. Their effect on replacement algorithms is therefore only indirect and through the increased insight that they teach relative to program behavior.
Further developments in this area are exemplified by the publication of L. P. Horwitz, R. M. Karp, R. E. Miller and S. Winograd, "Index Register Allocation," Journal of the ACM, Vol. 13, No. 1, January 1966, wherein there is provided an elegant solution to the general problem of index register allocation. Also, in U.S. Pat. No. 3,577,185 of L. A. Belady, "On-Line System for Measuring the Efficiency of Replacement Algorithms," issued May 4, 1971, and assigned to the IBM Corporation, there is described an on-line device for calculating approximate values for the minimum page fault count.
However, all of the prior art, as outlined hereinabove in the development of techniques for determining the minimum number of page faults, suffer from various disadvantages such as applicability in a particular type of environment, need for repetitious look-ahead, complexity, or inability to be employed in an on-line environment.
Accordingly, it is an important object of this invention to provide apparatus and a method for determining the behavior of replacement algorithms in a vertical memory system, specifically the minimum number of page faults, which is simple as compared to prior art techniques for accomplishing the same purpose, which can be employed with small amounts of information recorded or stored during processing, and which can be used on-line.
It is a further object to provide an apparatus and method in accordance with the preceding object wherein the need for providing for look-ahead is eliminated.
It is a further object to provide an apparatus and method in accordance with the preceding objects which enables the study of program structures in an operating environment.